"""
自己写的二分查找
[left,right]
注意边界问题
我自己用的是 “判断左右两个指针指的位置同target是否相等” 作为跳出循环的条件
"""
def search_yedongyu(lis, target):
    left = 0
    right = len(lis) - 1
    while lis[left] != target and lis[right] != target:
        mid = (left + right) // 2
        if lis[mid] > target:
            right = mid
        elif lis[mid] < target:
            left = mid
        else:
            return mid
        if left + 1 == right:
            return -1
    if lis[left] == target:
        return left
    if lis[right] == target:
        return right

"""
书上用的是 “左右两个指针是否相等” 作为跳出循环的条件
用这种方法，虽然不会出现数组的指针越界的错误
但是要思考一下为什么不会出现
1.当target正好在lis最后一个位置时：
    假如此刻 left += right, 并且right == len(lis) -1
    那么当计算出 mid = (left + fight) // 2时
    此时mid恰好等于left，那么肯定小于right
    此时left = mid + 1 ==> right
    那么会判断 lis[mid] == target
    
2. 当target的大小 是大于lis倒数第二个，但是小于倒数第一个时：
    假如此刻 left += right, 并且right == len(lis) -1
    那么当计算出 mid = (left + fight) // 2时
    此时mid恰好等于left，那么肯定小于right
    此时left = mid + 1 ==> right, 并且lis[mid] > target
    此时，right = mid - 1 = left -1 < left，跳出循环
    
当假设target 大于lis中的任意一个数，且left==right
此时lis[mid] < target
left + 1 = len(lis) > right
会发生数组越界吗，不会
因为书上用的方法，并没有使用left和right取数
"""
def search_web(lis, target):
    left = 0
    right = len(lis) - 1
    while left <= right:
        mid = (left + right) // 2
        if lis[mid] < target:
            left = mid + 1
        elif lis[mid] > target:
            right = mid - 1
        else:
            return mid
    return -1

if __name__ == "__main__":

    lis = [-2, 0, 4, 7, 9, 10, 11]
    target = 8
    print(search_web(lis, target))